The present application relates to a method and apparatus to determine the similarity or sufficient matching between two patterns or signal patterns, including the determination of the frequency and phase thereof.
Determining the degree of matching (similarity) between two signals is important in a number of applications. Typical examples include security systems, frequency analysis, image processing, and communications. Matching systems can be broadly divided into two categories—those that require two signals to be perfectly matched for some further action to take place, and those that are useable with only partial matching.
Security systems, for example, typically require perfect matching. In such systems, an input signal, such as a personal identification number (PIN) code punched into an automatic teller machine (ATM) by a user, requires that all digits are identical to a predetermined user code. If the two multi-digit numbers are not perfectly matched, the ATM will reject the user. In such systems, there is little use in permitting partial matching or similarity. If punching in only 3 out of 4 numbers were acceptable, multiple users could be charged with a transaction. Matchers of this type could easily be built as integrated circuits, where the output indicates which of a set of predetermined codes is identical, i.e., matched perfectly.
For other types of applications, the signals do not need to be identical, i.e., a perfect match. Rather, the application only requires a degree of similarity between the input signal and some other signal. For example, an image processing system could be used in conjunction with a camera to determine whether the camera is looking at a car or an airplane. Because “cars” and “airplanes” can include different types with dissimilar body shapes and colors, there is typically no such thing as a perfect match to a car or airplane, only a degree of similarity based upon comparisons of the input image against a set of test parameters, where each test parameter represents, for example, a specific car model viewed at a specific magnification and angle. If the degree of similarity for a particular test parameter exceeds some predetermined threshold level, a matcher may indicate a match. The match or similarity also may have a degree of confidence. With reference to the specific car above, the car may be identified as either model A or model B where model A has a higher degree of confidence because it resulted in more similarities than model B. Similarities may be a closer wheelbase, a closer chassis length or height, etc.
Other types of applications may compare a first signal (or unknown) with one or more test parameters. One particular type of application relates to frequency analysis, and in particular, measuring the frequency of an unknown signal. Depending upon the nature of the signal, this type of measurement can be approached in many ways. For simple periodic signals with little noise, i.e., if the signal-to-noise ratio (SNR) is large, such as >>0 dB, such as a sine wave, the solution can be as simple as measuring the time between zero-crossings of the signal to determine the frequency. If the SNR is low, which indicates high noise levels, this method fails because a signal can be driven across the zero point by the noise. For such cases, more complex detection techniques are required. These include conventional spectrum analysis tools, such as those available from numerous commercial vendors, including Hewlett-Packard, Tektronix, B&K Instruments, and others. Alternatively, an analog signal may be digitized so a computer can perform a fast Fourier transform (FFT) on the data. The squared magnitude of a complex FFT represents a histogram of frequency (or spectral power) content of the signal over an explicitly defined set of predetermined frequencies. For example, a 256 point FFT represents 128 unique frequency bins. Each frequency bin indicates the relative amount of power at the corresponding frequency.
Digital FFTs can be performed in hardware or in software and represents the most common method of analyzing the frequency content of a signal. Despite its popularity, the FFT also has certain significant drawbacks. FFT algorithms are relatively complex and are difficult to implement for “real-time” calculations. One potential problem is latency, i.e., a computational result may appear with a significant delay following input of the last data sample. A second problem is bottle-necking, i.e., data is read into the front end of the processor faster than it can be processed and read out. This may result in the need to discard potentially useful data while the processor is busy. A third issue relates to sampling speed and scalability to large data sets. With the high complexity of FFTs, it becomes expensive and difficult to design chips beyond, for example, N>1024. Similarly, it becomes difficult to implement processors in high speed semiconductor materials, such as GaAs. A further disadvantage of FFT approaches is that computation times increase very rapidly if the number of samples is not a power of 2. As a result, FFT processors typically use 128, 256, 512, etc., number of samples per transform.
An additional drawback with conventional FFT implementations is that dynamic updates of frequency spectra on a sample-to-sample basis cannot be done rapidly.
With the increased use of digital computers around 1970, researchers began considering binary correlators for implementation in integrated circuits to determine the similarity or degree of match between a first signal and one or more parameters. An example of such a correlator that uses serial and parallel shift registers to calculate correlations and convolutions is described in U.S. Pat. No. 4,161,033. Researchers also focused attention on a set of mathematical functions known as Walsh functions for a number of applications. For reviews, see, e.g., N. M. Blachman, “Sinusoids versus Walsh Functions”, IEEE Proc. 62, 346 (1974) and A. Deb et al., “Walsh Functions and their Applications: A Review”, IETE Technical Review, 9, 238 (1992). Walsh functions are similar to sines and cosines in the sense that they are periodic. However, rather than take on a continuous set of values, they only take on the values of +1 and −1. The idea of using such functions as the basis for digital calculations resulted in a significant body of work, but there appears to be no reference to the application of Walsh functions and a related transform (“the Walsh-Hadamard transform” or WHT) to the particular problem of calculating spectral content until 1996, when Lu (U.S. Pat. No. 5,566,100) was issued a patent implementing a Walsh-Hadamard transformation for frequency determinations.
Lu's technique requires two steps. First, the zero crossings of an AC signal are calculated in order to ensure that the sampling rate is large enough to meet the so-called Nyquist criterion. Following that first step, the second step comprises setting a suitable sampling rate and comparing the signal to a set of Walsh functions, in order to determine the signal frequency from the Walsh function having the same zero-crossing content as the signal.
A problem with this technique is that it assumes a high SNR, i.e., the signal must be “clean” enough that the first zero-crossing calculation is meaningful. In other words, the zero crossing is the result of the signal and not the noise. However, if the signals are clean enough that the number of zero crossings per unit time can be reliably calculated, there appears to be no need for the second step, because the rate of zero-crossings is by definition twice the signal frequency. In a more common case, the signal has a low SNR, which may be from significant amounts of wideband noise. In this case, simple zero-crossing calculations are not meaningful as the crossings (or lack thereof) may be the result of noise.
A second potential problem is that the Walsh functions are defined in terms of functions having the values+1 and −1, while conventional logic easily implemented in digital logic hardware has logical states of +1 and 0 (zero) corresponding to a high voltage and a zero voltage (for example, +5V and 0V in TTL logic). As a result of these issues, Lu's technique is not suitable for frequency extraction in a general case.
Accordingly, it would be advantageous to provide a method to the similarity or degree of match between two signals using binary logic to perform spectral and generalized correlation calculations, where the degree of similarity is indicated through a predetermined means, and where the signal-to-noise ratio does not have to be very large.
It would be further advantageous to provide a method to use such a matcher to measure the spectral content of a signal without invoking the complexities and other noted drawbacks of FFTs.
It would be further advantageous to provide a simple method that can be implemented in hardware, such as a single integrated circuit chip.
It would be further advantageous to provide a method for such implementation that allows for direct use of binary+1/0 logic.
It would be further advantageous to provide a method that permits simpler scaling to higher frequency resolutions than conventional FFT algorithms.
It would be further advantageous to provide a method that permits implementations of the algorithm requiring a minimum number of logic gates.
It would be further advantageous to provide a method that permits simple implementation in high-speed semiconductor materials.
It would be further advantageous to provide a method that permits rapid calculation of spectral information from an arbitrary number of samples, not simply sequences containing a power of 2 samples.
It would be further advantageous to provide a method that permits a continuous update of spectra without recalculation of an entire spectral transform.
It would be further advantageous to provide a method that permits averaging over any number of N-length sequences without further computational hardware or software, in order to improve the confidence and accuracy of matches.
It would be further advantageous to provide a multiple channel implementation where the detection of similarities is not dependent on inter-cell timing considerations.
It would be further advantageous to provide a multiple channel implementation where the frequency relationship and bandwidth of the channels is independent and flexible
It would be further advantageous to provide a method that permits, independent patterns in each channel for rapid pattern detection not requiring post processing in the frequency domain.